package com.example.algorithm.backtrcaking.backrewrite;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/20
 * 组合数3
 */
public class ZuHeThree {

    public List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> list=new ArrayList<>();
        Deque<Integer> deque=new LinkedList<>();

        backTracking(list,deque,n,k,1,0);

        return list;
    }

    private void backTracking(List<List<Integer>> list, Deque<Integer> deque, int n, int k, int startIndex, int sum) {

        if(sum>n)
        {
            return;
        }
        if(sum==n&&deque.size()==k)
        {
            list.add(new ArrayList<>(deque));
            return;
        }

        for(int i=startIndex;i<=10-(k-deque.size());i++)
        {
            deque.addLast(i);
            sum+=i;
            backTracking(list, deque, n, k, i+1, sum);
            sum-=i;
            deque.removeLast();
        }
    }


    public static void main(String[] args) {
        ZuHeThree zuHeThree = new ZuHeThree();
        List<List<Integer>> listList = zuHeThree.combinationSum3(3, 9);
        listList.stream().forEach(System.out::println);
    }
}
